1. Field of the Invention
The present invention relates to technology for encoding multi-level image data divided into a multiplicity of blocks each of which includes a number of pixels (for example 8·8 pixels; 8·8 read “8-by-8”), which encoding follows an orthogonal transformation that is performed on tone values of the pixels in each of the multiple blocks.
2. Description of the Related Art
Generally, tone values of each pixel in image data, especially halftone or color image data that has a far larger data volume than numeric data, should be effectively encoded in order to be retained and sent at high quality and at high speed.
An encoding method of the JPEG (Joint Photographic Expert Group) is known as a method for effectively encoding image data. The JPEG method comprises the following steps of: dividing image data representing a source image into a multiplicity of blocks each of which includes 8·8 pixels; performing a two-dimensional discrete cosine transform (hereinafter called a DCT transformation) on signals of each of the multiple blocks to transform the signals into DCT coefficients distributed over the spatial frequencies; quantizing the DCT coefficients using threshold values adapted to human visual perception to obtain quantized DCT coefficients; and encoding the quantized DCT coefficients using one or more statistically-obtained Huffman tables.
An accompanying drawing FIG. 10 is a block diagram schematically showing a conventional JPEG encoding circuit, as shown in accompanying drawing FIG. 10, which comprises inputting terminal 31, two-dimensional DCT converter 32, linear quantizing section 33, quantization matrix 34, variable-length encoding section 35, coding table (Huffman tables) 36, and outputting terminal 37.
Image data of an encoding target is divided into a multiplicity of blocks each of which includes 8·8 pixels (an example of a block is shown in accompanying drawing FIG. 11) and then the image data in the form of tone values is inputted to two-dimensional DCT converter 32 via inputting terminal 31. Upon receipt of the tone values, two-dimensional DCT converter 32 performs a DCT transformation of an orthogonal transformation on the tone values of each block shown in FIG. 11 so that the tone values are converted into DCT coefficients distributed over the spatial frequencies as shown in accompanying drawing FIG. 12. After that, two-dimensional DCT converter 32 outputs the DCT coefficients to linear quantizing section 33.
Linear quantizing section 33 multiplies each of 8·8 elements of quantization matrix 34 predefined based on the result of visual experiments by a quantization adjusting parameter to thereby obtain a quantization threshold value corresponding to each element and performs linear quantization by dividing the DCT coefficients from two-dimensional DCT converter 32 by the obtained quantization threshold values to obtain quantized DCT coefficients. Quantization matrix 34 is as shown in accompanying drawing FIG. 13 formed by 8·8 threshold values, for example. DCT coefficients of FIG. 12 are linear quantized using quantization matrix 34 so that linear quantizing section 33 creates quantized DCT coefficients shown in accompanying drawing FIG. 14. Linear quantization makes quantization DCT coefficients generated from DCT coefficients smaller than the corresponding threshold value become zero as shown in FIG. 14. Therefore, non-zero quantized DCT coefficients of each block are DC coefficients (a value indicates the total level, “five” in FIG. 14) and a small number of AC coefficients (five AC coefficients in FIG. 14).
The quantized DCT coefficients arranged in two dimensions are converted into one-dimensional serial data by zig-zag ordering scanning as shown in accompanying drawing FIG. 15, and the serial data is inputted to variable-length encoding section 35. Variable-length encoding section 35 performs a variable-length coding on the difference between the DC coefficients that is the first piece of serial data of each block and the DC coefficients of the block immediately before. Further, variable-length encoding section 35 performs variable-length encoding on values of valid AC coefficients that are not zero (hereinafter the values are called “indexes”) and on the length of run between an index and invalid coefficients whose values are zero (hereinafter a length is simply called a “run”). Variable-length encoding section 35 encodes each of the DC and AC coefficients using coding table 36 in the form of one or more Huffman tables created in accordance with the statistical data volume of each image. The thus obtained encoded data is sequentially output from outputting terminal 37.
In a JPEG technique, image data sometimes has to be encoded to a desired data volume, in other words, the volume of encoded image data has to be the desired data volume. This occurs when the encoded image data representing a predetermined number of source images is to be stored in a recording medium of limited volume, such as an IC memory or a flexible disc.
Conventionally, the following manner of controlling encoding has been proposed so that image data is encoded to a desired data volume. As described above, quantization and subsequent variable-length encoding are performed on DCT coefficients to thereby obtain a volume of encoded data. If the encoded data volume is different from a desired data volume, coarseness of quantization (i.e., quantization threshold values) is changed and quantization and variable-length encoding are performed again. In the same manner, changing threshold values, quantization, variable-length encoding repeat until the image data is encoded to the desired data volume.
In the above-mentioned manner, the relationship between a volume of encoded image data and coarseness of quantization is obtained by performing variable-length encoding at least once so that the same image data is encoded to a desired data volume. The obtained relationship is used to determine coarseness of quantization, which is used to encode the image data to the desired data volume. This means that control between quantization and variable-length encoding is performed in a feed-back manner, which results in complicated processes. Further, since variable-length encoding takes a long time, it is time-consuming to determine an appropriate coarseness of quantization, i.e., to obtain an encoded image data of a desired data volume. Especially in the above case, variable-length encoding may be repeated several times whereupon an extremely long time is required to complete the processes.
As a solution, Japanese Patent Registration No. 2820807 discloses the following method of encoding image data. For example, a JPEG encoding circuit to which the encoding method is applied includes, as shown in accompanying drawing FIG. 16, two-dimensional DCT converter 1 , DCT coefficient retaining section 2, linear quantizing section 3, quantized DCT coefficient retaining section 4, coding table 5, variable-length encoding section 6, valid coefficient counter 7, and data volume adjusting section 8.
Two-dimensional DCT converter 1 receives image data PCS divided into the multiple blocks each of which has 8·8 pixels and then performs an orthogonal transformation on each block of the image data PCS by a DCT transformation, in the same manner performed in two-dimensional DCT converter 32 of FIG. 10, to thereby obtain 8·8 DCT coefficients distributed over spatial frequencies. DCT coefficient retaining section 2 temporarily retains the 8·8 DCT coefficients of each block obtained in two-dimensional DCT converter 1.
Linear quantizing section 3 receives the 8·8 DCT coefficients of each block from DCT coefficient retaining section 2 and performs linear quantization on the 8·8 DCT coefficients, likewise the linear quantizing section 33 of FIG. 10, to output quantized DCT coefficients. Linear quantizing section 3 includes divider 3a, which divides 8·8 DCT coefficients per block by quantization threshold values q(i) (each q(i) is an integer equal to or greater than “0”, i=0, 1, . . . , 63), each of which corresponds to one of the 8·8 DCT coefficients to thereby quantize the 8·8 DCT coefficients.
Quantized DCT coefficient retaining section 4 temporarily retains 8·8 quantized DCT coefficients of each block obtained by linear quantizing section 3. Coding table 5 takes the form of one or more Huffman tables in the same way as coding table 36 of FIG. 10.
Variable-length encoding section 6 receives one-dimensional serial data, which is the result of conversion by zig-zag ordering scanning performed on the two-dimensional 8·8 quantized DCT coefficients of each block, from quantized DCT coefficient retaining section 4 and encodes the quantized DCT coefficients using coding table 5 in the same in which the coefficients are received, in the same manner as variable-length encoding section 35 of FIG. 10.
Valid coefficient counter 7 counts the total number n of valid coefficients (non-zero quantized DCT coefficients) among the quantized DCT coefficients of the entire image data by adding the 8·8 quantized DCT coefficients of each block.
Data volume adjusting section 8 determines quantization threshold values q(i) in accordance with the total number n of valid coefficients, and adjusts a data volume of the quantization coefficients in such a manner that the valid coefficients of the entire image data is to be encoded to a desired data volume F. Data volume adjusting section 8 includes data-volume/valid-coefficient changing section 81 and quantization threshold value determining section 82.
Data-volume/valid-coefficient changing section 81 converts the desired data value F into the total number m of valid coefficients to be allocated to the entire image data representing a source image. Since a data volume of encoded quantization coefficients (bit per pixel) is proportional to the average number of valid coefficients per block consisting of 8·8 pixels as shown in accompanying drawing FIG. 17, data-volume/valid-coefficient changing section 81 computes the total number m of valid coefficients to be allocated to the entire image data which number conforms to the desired data volume F based on the proportionate relationship.
Quantization threshold value determining section 82 determines quantization threshold values q(i) based on the difference between the total number n obtained by valid coefficient counter 7 and the total number m obtained by data-volume/valid-coefficient changing section 81. Quantization threshold value determining section 82 comprises quantization threshold value retaining section 82a, scaling controller 82b and multiplier 82c. 
Quantization threshold value retaining section 82a retains 8·8 quantization threshold values Q(i) (each Q(i) is an integer equal to or greater than “0”, i=0, 1, . . . , 63), which are predefined.
Scaling controller 82b determines, in accordance with the difference between the total number n obtained by valid coefficient counter 7 and the total number m obtained by data-volume/valid-coefficient changing section 81, a scaling factor SF used for scaling the predefined quantization threshold values Q(i).
Multiplier 82c scales the predefined quantization threshold values Q(i) by multiplying a scaling factor SF determined by scaling controller 82b and the predefined quantization threshold values Q(i) retained in quantization threshold value retaining section 82a. The scaled quantization threshold values Q(i) are regarded as actual quantization threshold values q(i) and are input to divider 3a in linear quantizing section 3.
Quantization threshold values q(i) become greater (in other words, quantization becomes coarser) in accordance with an increase in a scaling factor SF whereupon the total number n of valid coefficients is reduced. On the other hand, quantization threshold values q(i) become smaller (i.e., quantization becomes less grainy) in accordance with a decrease in a scaling factor SF whereupon the total number n of valid coefficients increases. Namely, a scaling factor SF is inversely proportional to the total number of valid coefficients as shown in accompanying drawing FIG. 18. Therefore, if the difference between the total numbers n and m is outside a predefined allowable range and at the same time n is larger than m (i.e., n>m), scaling controller 82b sets a scaling factor SF to be large. Conversely, if the difference between n and m is outside the allowable range and n is smaller than m (i.e., n<m), a scaling factor SF is set to be small.
An operation performed in the JPEG encoding circuit of FIG. 16 will now be described. The JPEG encoding circuit determines quantization threshold values q(i) by undertaking the following succession of procedural steps (1) through (13), which quantization threshold values q(i) cause a data volume of image data on which variable-length encoding is performed to be substantially identical to the desired data volume F. In this regard, a scaling factor SF is initialized to “1”.
Step (1): Two-dimensional DCT converter 1 receives image data PCS divided in a multiplicity of blocks each of which consists of 8·8 pixels, performs an orthogonal transformation on each block by DCT transformation in order to obtain 8·8 DCT coefficients and stores the 8·8 DCT coefficients in DCT coefficient retaining section 2.
Step (2): data-volume/valid-coefficient changing section 81 computes the total number m of valid coefficients to be allocated to the entire image data based on a desired data volume F designated by a user or the like and the proportionate relationship of FIG. 17, and inputs the computed total number m to scaling controller 82b. 
Step (3): DCT coefficient retaining section 2 sequentially outputs the retained DCT coefficients one by one to divider 3a of linear quantizing section 3 in accordance with individual data reading signals RDT issued from a non-illustrated timing controller.
Step (4): Concurrently with reading the individual DCT coefficient, multiplier 82c multiplies the predefined quantized threshold value Q(i) which is associated with the DCT coefficient and which is read from quantization threshold value retaining section 82a by the initial scaling factor SF of “1”, which is output from scaling controller 82b. The result of the multiplication is regarded as quantization threshold value q(i) associated with the DCT coefficient and is input to divider 3a. 
Step (5): Divider 3a divides the DCT coefficient received from DCT coefficient retaining section 2 by the associated quantization threshold value q(i). The resultant quantized DCT coefficient is output to quantized DCT coefficient retaining section 4 and valid coefficient counter 7.
Step (6): Valid coefficient counter 7 counts up non-zero coefficients (i.e., valid coefficients) among the quantized DCT coefficients received from divider 3a in order to count the number of valid coefficients of each block, and retains the counted number therein.
Step (7): Upon completion of quantization on a DCT coefficient, the timing controller instructs DCT coefficient retaining section 2 to read a next DCT coefficient. Steps (4) to (6) are performed on the next DCT coefficient.
Step (8): Steps (3) to (7) are performed on all blocks that constitute the entire image data so that valid coefficient counter 7 obtains the total number n of valid coefficients of the entire image data.
Step (9): The total number n obtained by valid coefficient counter 7 is input to scaling controller 82b. 
Step (10): Scaling controller 82b determines, based on a difference between the total number m of valid coefficients associated with the desired data volume F and the total number n obtained by valid coefficient counter 7, whether or not the scaling factor SF is to be updated.
Step (11): Scaling controller 82b completes updating of the scaling factor SF if the difference between n and m is inside the predefined allowable range. While, if the difference is outside the allowable range and n is greater than m (i.e., n>m), scaling controller 82b increases the scaling factor by a certain amount; and if the difference is outside the allowable range and n is smaller than m (i.e., n<m), scaling controller 82b decreases the scaling factor SF by a certain amount.
Step (12): If a scaling factor SF is updated, the total number n retained in valid coefficient counter 7 is cleared to zero and procedural steps (3) to (11) repeat until a difference between the total numbers m and n falls within the allowable range.
Step (13): At the time the difference between n and m come to be within the allowable range, updating of the scaling factor SF is completed. DCT coefficients are quantized using quantization threshold values q(i) obtained on the basis of the resultant updated scaling factor, and thereby converted into quantized DCT coefficients, on which variable-length encoding section 6 performs variable-length encoding using coding table 5.
As described above, the JPEG encoding circuit of FIG. 16 counts the total number n of valid coefficients among quantized DCT coefficients obtained by quantizing on the entire image data, and determines quantization threshold values q(i) based on the total number n thus counted and the estimated total number m corresponding to the desired data volume F. Therefore, it is possible to determine quantization threshold values q(i) which cause the image data to be encoded to the desired data volume F without actually performing variable encoding.
However, since the JPEG encoding circuit of FIG. 16 determines quantization threshold vales q(i) based on the total number n of valid coefficients of the entire image data that is a target of encoding, the entire image is assumed to have constant features whereupon encoding is not performed in accordance with changes in tone or the like over the entire image data. Namely, a conventional encoding technique determines features of the entire image based on the total number n of valid coefficients appearing over the entire image data. For this reason, a landscape image whose center portion gradually varies in tone tends to be encoded coarsely because of features of the remaining portion so that an encoded image data volume cannot be accurately adjusted.
In the method for encoding image data performed by the JPEG encoding circuit of FIG. 16, variable-length encoding section 6 performs variable-length encoding once, but quantization performed by linear quantizing section 3 repeats until a difference between n and m comes to be within the allowable range. Completion of encoding in the JPEG encoding circuit of FIG. 16 requires in excess of 1.5 times longer time than that required for both quantization by linear quantizing section 3 and encoding by variable-length encoding section 6 once. Therefore, demands for alternative methods and circuits that reduce the time required have arisen.